package datastructure.sparsearray;

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020-03-18
 */
public class SparseArray {

    public static void main(String[] args) {
        // 创建一个原始二维数组 11 * 11
        int[][] chessArr = initChessArr(11, 11);
        // 输出原始数组
        System.out.println("输出原始数组~~~~");
        printArray(chessArr);

        // 将二维数组转换稀疏数组
        int[][] sparseArray = chessArrToSparseArray(chessArr);
        // 输出稀疏数组
        System.out.println();
        System.out.println("输出原始二维数组的稀疏数组~~~~");
        printArray(sparseArray);

        // 将稀疏数组转换原始二维数组
        int[][] chessArr1 = sparseArrayToChessArr(sparseArray);
        System.out.println("输出稀疏数组转换后的原始二维数组~~~~");
        // 输出返回后的原始二维数组
        printArray(chessArr1);
    }


    /**
     * 初始原始二维数组
     *
     * @param rowNum 行
     * @param colNum 列
     * @return 二维数组
     */
    private static int[][] initChessArr(int rowNum, int colNum) {
        // 0表示没有棋子 1表示白色棋子 2表示黑色棋子
        int[][] chessArr = new int[rowNum][colNum];
        chessArr[1][2] = 1;
        chessArr[2][3] = 2;
        return chessArr;
    }

    /**
     * 二维数组转换稀疏数组
     *
     * @param chessArr 二维数组
     * @return 稀疏数组
     */
    private static int[][] chessArrToSparseArray(int[][] chessArr) {
        // 1、遍历得到非0数据个数
        int valSum = 0;
        for (int[] row : chessArr) {
            for (int data : row) {
                if (data != 0) {
                    valSum++;
                }
            }
        }
        // 2、创建稀疏数组
        int[][] sparseArray = new int[++valSum][3];
        // 3、给稀疏数组赋值第一行
        sparseArray[0][0] = chessArr.length;
        sparseArray[0][1] = chessArr[0].length;
        sparseArray[0][2] = valSum;

        int count = 0;
        for (int i = 0; i < chessArr.length; i++) {
            for (int j = 0; j < chessArr[0].length; j++) {
                if (chessArr[i][j] != 0) {
                    count++;
                    // 记录行
                    sparseArray[count][0] = i;
                    // 记录列
                    sparseArray[count][1] = j;
                    // 记录值
                    sparseArray[count][2] = chessArr[i][j];
                }
            }
        }
        return sparseArray;
    }

    /**
     * 将稀疏数组转换原始二维数组
     *
     * @param sparseArray 稀疏数组
     * @return 原始二维数组
     */
    private static int[][] sparseArrayToChessArr(int[][] sparseArray) {
        // 1、创建二维数组 行列记录在稀疏数组第一行中
        int[][] chessArr1 = new int[sparseArray[0][0]][sparseArray[0][1]];
        // 2、恢复数据
        for (int i = 1; i < sparseArray.length; i++) {
            // 第一列是所在行 第二列是所在列 第三列是原始值
            chessArr1[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }
        return chessArr1;
    }

    /**
     * 打印二维数组
     *
     * @param array 二维数组
     */
    private static void printArray(int[][] array) {
        for (int[] row : array) {
            for (int data : row) {
                System.out.print(data + "\t");
            }
            System.out.println();
        }
    }
}
